package main

import (
	"fmt"
)

func main() {
	mainString :="abcxabcdabxabcdabcdabcy"
	// subString := "abcdab";
	// subString :="abcdabc"
	subString :="abcdabcy"
	next := computeNextArray(subString);
	fmt.Println("next----", next)
	idx := KMP(mainString, subString);
	fmt.Println("子串在主串中第一次出现的位置", idx)
}


/**
KMP 
**/
func  KMP(mainString string, subString string) int{
	mainIdx :=0;
	subIdx :=0;
	mainLen :=len(mainString)
	subLen := len(subString)
	next := computeNextArray(subString);
	for  {
		if mainIdx>=mainLen  || subIdx >= subLen{
			//当子串匹配完, 说明主串中包含子串, 需要结束
			//当主串匹配完, 不管子串有没有结束, 都应该不再匹配
			break;
		}

		if mainString[mainIdx] == subString[subIdx]{
			//字符匹配的时候, 主串和子串都往后走
			mainIdx ++;
			subIdx ++;
		}else{
			//不相等的时候, 子串切换到next数组中对应的前一个元素对应的, 需要位移的下标, 进行重新匹配
			if subIdx != 0{
				subIdx = next[subIdx-1]
			}else{
				//当主串元素与子串元素不一样, 且子串回退到了首字符时, 检查主串的下一个字符
				mainIdx++
			}

		}
	}

	//判断结果
	if subIdx>=subLen{
		//说明子串匹配完了, 子串在主串中存在
		return mainIdx - subLen
	}
	//其他情况下, 说明子串没走完, 返回 -1
	return -1

}



//computeNextArray 用于计算子串的 next 数组
func computeNextArray(subString string) []int {
	next := make([]int, len(subString))
	index :=0; 
	i := 1;
	for i < len(subString){
		if subString[i] == subString[index]{
			next[i] = index + 1
			i ++ ;
			index ++;
		}else{
			//不相等的时候
			if index != 0{
				//当index != 0 的时候, 把 next 中, index 前一个元素对应的 next中的值, 赋给 index  
				index = next[index -1]
			}else{
				//当index = 0 的时候,  subString[i] 和 subString[0] , 也就是subString 首字母不相同, 则i向后走
				i++
			}
		}
	}
	return next
}


